package linkList;

/**
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
public class N206_ReverseLinkList {
    /**
     * 双指针法
     */
    public ListNode reverseList_DoublePtr(ListNode head) {
        ListNode cur = head, pre = null, temp = null;
        while (cur != null) {
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 递归法
     */
    public ListNode reverseList_Recursion(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode pre, ListNode cur) {
        if (cur == null) return pre;
        ListNode temp = cur.next;
        cur.next = pre;
        return reverse(cur, temp);
    }


    public static void main(String[] args) {
        N206_ReverseLinkList solution = new N206_ReverseLinkList();
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ListNode head = ListNode.generaListByArray(arr);
        head = solution.reverseList_Recursion(head);
        ListNode.printList(head);
    }
}
